package alo.p6.work4;

import alo.p6.BinarySearchTreeNode;

/**
 * @ClassName KthSmallestInBST
 * @Description 寻找二叉搜索树中第k大的结点
 * @Author Fanxc
 * @DATE 2021/2/22 15:28
 * @Version 1.0
 */
public class KthSmallestInBST {
    //利用中序遍历，寻找第k大的结点
    BinarySearchTreeNode kthSmallestInBST(BinarySearchTreeNode root,int k,int count){
        if (root==null){
            return null;
        }
        BinarySearchTreeNode left=kthSmallestInBST(root.getLeft(),k,count);
        //如果左子树中有，直接返回
        if (left!=null){
            return left;
        }
        if (count++ ==k){
            return root;
        }
        return kthSmallestInBST(root.getRight(),k,count);
    }
}
